#include <stdio.h>
#include <stdlib.h>
typedef enum tag
{
    link,
    thread
};
typedef struct clue_T
{
    tag ltag;
    tag rtag;
    int data;
    struct clue_T *left;
    struct clue_T *right;
};
//1.creat_tree
void creat_tree(clue_T *&root, int a[], int len, int index)
{
    if (index < len)
    {
        if (a[index])
        {
            root = (clue_T *)malloc(sizeof(clue_T));
            root->data = a[index];
            root->right = root->left = NULL;
            root->ltag = root->rtag = link;
            creat_tree(root->left, a, len, 2 * index + 1);
            creat_tree(root->right, a, len, 2 * index + 2);
        }
        else
        {
            root = NULL;
        }
    }
}
//1.1 mid_order_visit()
void mid_order_visit(clue_T *root)
{
    if (root)
    {
        mid_order_visit(root->left);
        printf("%3d", root->data);
        mid_order_visit(root->right);
    }
}
//2.creat_clue_tree
void clue(clue_T *node);
clue_T *pre; //global varible
clue_T *creat_clue_tree(clue_T *&root)
{
    clue_T *head = (clue_T *)malloc(sizeof(clue_T));
    if (root)
    {
        pre = head;
        head->ltag = link;
        head->left = root;
        head->rtag = thread;
        head->right = head;
        clue(root);
        head->right = pre;
        pre->rtag = thread;
        pre->right = head;
    }
    else //root==NULL
    {
        head->ltag = head->rtag = thread;
        head->left = head->right = head;
    }
    return head;
}
void clue(clue_T *node)
{
    if (node)
    {
        clue(node->left);
        if (!pre->right)
        {
            pre->right = node;
            pre->rtag = thread;
        }
        if (!node->left)
        {
            node->ltag = thread;
            node->left = pre;
        }
        pre = node;
        clue(node->right);
    }
}
//3.clue_vist()
void clue_visit(clue_T *head)
{
    clue_T *p = head;
    while (p->ltag != thread)
    {
        p = p->left;
    }
    while (p != head)
    {
        printf("%3d", p->data);
        p = p->right;
    }
}
//4.opposit
void op_clue_visit(clue_T *head)
{
    clue_T *p = head->right;
    while (p != head)
    {
        //visit right_subtree
        while (p->rtag == link)
            p = p->right;
        printf("%3d", p->data);
        while (p->ltag == thread && p->left != head)
        {
            p = p->left;
            printf("%3d", p->data);
        }
        p = p->left;
    }
}
int main()
{
    /*******************code*******************/
    int a[] = {1, 2, 3, 4, 5, NULL, 7, NULL, 8};
    clue_T *root;
    creat_tree(root, a, 9, 0);
    printf("mid_order_visit:\n");
    mid_order_visit(root);
    clue_T *head = creat_clue_tree(root);
    printf("\nclue_visit:\n");
    clue_visit(head);
    op_clue_visit(head);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
